//数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 
//
// 
//
// 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 
//
// 
//
// 示例 1: 
//
// 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
//输出: 2 
//
// 
//
// 限制： 
//
// 1 <= 数组长度 <= 50000 
//
// 
//
// 注意：本题与主站 169 题相同：https://leetcode-cn.com/problems/majority-element/ 
//
// 
// Related Topics 数组 哈希表 分治 计数 排序 👍 240 👎 0

package com.cute.leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

public class ShuZuZhongChuXianCiShuChaoGuoYiBanDeShuZiLcof {
    public static void main(String[] args) {
        Solution solution = new ShuZuZhongChuXianCiShuChaoGuoYiBanDeShuZiLcof().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 直接计数的方法时间空间都很差劲
         */
        public int majorityElement1(int[] nums) {
            int tar = (nums.length & 1) == 1 ? (nums.length / 2) + 1 : nums.length / 2;// 奇偶长度不同阈值也不同
            Map<Integer, Integer> map = new HashMap<>();
            for (int num : nums){
                map.put(num, map.getOrDefault(num, 0) + 1);
                if (map.get(num) >= tar) return num;
            }
            return nums[nums.length - 1];// 这里是按照测试用例试出来的
        }
        /**
         * 既然是求众数，那就看谁最后能保留下来
         * 相同的数计数+1，不同的数计数-1
         * 计数为0后更新res，这样由于众数最多，最后剩下的一定是众数
         */
        public int majorityElement(int[] nums) {
            int count = 0;// 计数
            int res = -1;// 众数
            for (int num : nums){
                if (count == 0){
                    count++;
                    res = num;
                }else if (num == res) count++;
                else count--;
            }
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}